package leetcode;

public class AddTwo {

    public static void main(String[] args) {
        ListNode node1 = create(9, 8);
        ListNode node2 = create(1);
        ListNode result = addTwoNumbers(node1, node2);
        while (result != null) {
            System.out.print(result.val);
            result = result.next;
        }
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = null;
        ListNode point = null;
        int d = 0;
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + d;
            d = sum / 10;
            ListNode tmp = new ListNode(sum % 10);
            if (result == null) {
                result = tmp;
                point = result;
            } else {
                point.next = tmp;
                point = point.next;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        point.next = l1 == null ? l2 : l1;
        if (d != 0) {
            if (point.next == null)
                point.next = new ListNode(d);
            else
                plusOne(point.next);
        }
        return result;
    }

    public static void plusOne(ListNode node) {
        int sum = node.val + 1;
        node.val = sum % 10;
        if (sum >= 10) {
            if (node.next != null)
                plusOne(node.next);
            else
                node.next = new ListNode(1);
        }
    }

    public static ListNode create(int... values) {
        ListNode result = null;
        ListNode point = null;
        for (int i = 0; i < values.length; i++) {
            ListNode tmp = new ListNode(values[i]);
            if (i == 0) {
                result = tmp;
                point = result;
            } else {
                point.next = tmp;
                point = point.next;
            }
        }
        return result;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
